<cfcomponent hint="I solve Sudoku puzzles with the power of QoQ!" implements="ISudokuSolver" output="false">

<cffunction name="init" returntype="ISudokuSolver" access="public" hint="Perform any necessary initialization; must be called before any other methods.">
	<cfset setTermCount(9)>
	<cfset clearPuzzle()>
	<cfreturn this>
</cffunction>

<cffunction name="buildDefaultBoxes" returnType="void" access="private">
	<cfargument name="termCount" type="Numeric" required="yes">
	<cfset var q = queryNew("rowNum,colNum,boxNum","Integer,Integer,Integer")>
	<cfset var r = "">
	<cfset var c = "">
	<cfset var b = "">
	<cfset var s = int(sqr(Variables.termCount))>
	<cfloop from="1" to="#Arguments.termCount#" index="r">
		<cfloop from="1" to="#Arguments.termCount#" index="c">
			<cfset b = int((int((r - 1) / s) * s) + int((c - 1) / s) + 1)>
			<cfset queryAddRow(q)>
			<cfset querySetCell(q, "rowNum", r, q.recordCount)>
			<cfset querySetCell(q, "colNum", c, q.recordCount)>
			<cfset querySetCell(q, "boxNum", b, q.recordCount)>
		</cfloop>
	</cfloop>
	<cfset Variables.boxesValid = true>
	<cfset Variables.cellToBox = q>
</cffunction>

<cffunction name="setTermCount" returntype="boolean" access="public" hint="Set the number of terms/digits/letters to be used in the puzzle, returning TRUE for success or FALSE for an unacceptable count." output="false">
	<cfargument name="termCount" type="Numeric" required="yes">
	<cfset var i = 0>
	<cfif (Arguments.termCount lt 1) or (Arguments.termCount gt 9) or (int(Arguments.termCount) neq Arguments.termCount)>
		<cfreturn false>
	</cfif>
	<cfset Variables.termCount = Arguments.termCount>
	<cfset Variables.terms = queryNew("termNum", "Integer")>
	<cfloop from="1" to="#Variables.termCount#" index="i">
		<cfset queryAddRow(Variables.terms)>
		<cfset querySetCell(Variables.terms, "termNum", i, i)>
	</cfloop>
	<cfset buildDefaultBoxes(Variables.termCount)>
	<cfreturn true>	
</cffunction>

<cffunction name="solvePuzzle" returntype="query" access="public" hint="Run solving algorithm, returning a query of deductions with columns (ROW,COL,BOX,TERM).">
	<cfset var deduced = "">
	<cfset var knowns = "">
	<cfset var grid = "">
	<cfset var box = Variables.cellToBox>
	<cfset var terms = Variables.terms>
	<cfset var elim = "">
	<cfset var iteration = 0>
	<cfset var done = false>
	<cfquery name="knowns" dbtype="query">
	SELECT rowNum, colNum, boxNum, termNum, 0 AS Iter
	FROM Variables.givenCells
	</cfquery>
	<cfquery name="deduced" dbtype="query">
	SELECT rowNum AS Row, colNum AS Col, boxNum AS Box, termNum AS Term, Iter
	FROM knowns
	</cfquery>
	<cfset elim = knowns>
	<!--- Build a complete grid --->
	<cfquery name="grid" dbtype="query">
	SELECT box.rowNum, box.colNum, box.boxNum, terms.termNum
	FROM box, terms
	</cfquery>
	<cfloop condition="not done">
		<cfset iteration = iteration + 1>
		<!--- Eliminate knowns --->
		<cfquery name="grid" dbtype="query">
		SELECT rowNum, colNum, boxNum, termNum
		FROM grid
		WHERE NOT (
		    <cfloop query="elim"><cfif currentRow gt 1>OR</cfif>
			((rowNum = #rowNum#) AND (colNum = #colNum#) AND (termNum != #termNum#))
			OR (((rowNum = #rowNum#) OR (colNum = #colNum#) OR (boxNum = #boxNum#)) AND (termNum = #termNum#))
			</cfloop>
		  )
		</cfquery>
		<cfquery name="elim" dbtype="query">
		SELECT rowNum, colNum, MIN(boxNum) AS boxNum, MIN(termNum) AS termNum
		FROM grid
		GROUP BY rowNum, colNum
		HAVING COUNT(*) = 1
		</cfquery>
		<cfif elim.recordCount gt 0>
			<cfquery name="deduced" dbtype="query">
			SELECT Row, Col, Box, Term, Iter
			FROM deduced
			UNION ALL
			SELECT rowNum AS Row, colNum AS Col, boxNum AS Box, termNum AS Term, #iteration# AS Iter
			FROM elim
			</cfquery>
		<cfelse>
			<cfset done = true>
		</cfif>
	</cfloop>
	<cfreturn deduced>
</cffunction>

<cffunction name="clearPuzzle" returntype="void" access="public" hint="Remove all givens and deductions, leaving adjusted boxes intact, resetting the puzzle to an empty state.">
	<cfset Variables.givenCells = queryNew("rowNum,colNum,boxNum,termNum","Integer,Integer,Integer,Integer")>
</cffunction>

<cffunction name="addGiven" returntype="boolean" access="public" hint="Add a given term to a cell, returning TRUE for an acceptable value or FALSE for an unacceptable value.">
	<cfargument name="rowNum" type="Numeric" required="yes">
	<cfargument name="colNum" type="Numeric" required="yes">
	<cfargument name="termNum" type="Numeric" required="yes">
	<cfset var r = Arguments.rowNum>
	<cfset var c = Arguments.colNum>
	<cfset var t = Arguments.termNum>
	<cfset var b = boxFromCell(r, c)>
	<cfset var q = "">
	<cfif not (inRange(r) and inRange(c) and inRange(t))>
		<cfreturn false>
	</cfif>
	<cfquery name="q" dbtype="query">
	SELECT 1
	FROM Variables.givenCells
	WHERE ((rowNum = <cfqueryparam value="#r#" cfsqltype="cf_sql_integer">) AND (colNum = <cfqueryparam value="#c#" cfsqltype="cf_sql_integer">))
	  OR ((rowNum = <cfqueryparam value="#r#" cfsqltype="cf_sql_integer">) AND (termNum = <cfqueryparam value="#t#" cfsqltype="cf_sql_integer">))
	  OR ((colNum = <cfqueryparam value="#c#" cfsqltype="cf_sql_integer">) AND (termNum = <cfqueryparam value="#t#" cfsqltype="cf_sql_integer">))
	  OR ((boxNum = <cfqueryparam value="#b#" cfsqltype="cf_sql_integer">) and (termNum = <cfqueryparam value="#t#" cfsqltype="cf_sql_integer">))
	</cfquery>
	<cfif q.recordCount gt 0>
		<cfreturn false>
	</cfif>
	<cfset queryAddRow(Variables.givenCells)>
	<cfset querySetCell(Variables.givenCells, "rowNum", r, Variables.givenCells.recordCount)>
	<cfset querySetCell(Variables.givenCells, "colNum", c, Variables.givenCells.recordCount)>
	<cfset querySetCell(Variables.givenCells, "boxNum", b, Variables.givenCells.recordCount)>
	<cfset querySetCell(Variables.givenCells, "termNum", t, Variables.givenCells.recordCount)>
	<cfreturn true>
</cffunction>

<cffunction name="validateBoxes" returntype="boolean" access="public" hint="Ensure that the adjusted box pattern is acceptable, returning TRUE for acceptable or FALSE for not; must be called after all setCellBox() calls are complete.">
	<cfset var q = "">
	<cfquery name="q" dbtype="query">
	SELECT boxNum + 0 AS boxNum, COUNT(*) AS cells
	FROM Variables.cellToBox
	GROUP BY boxNum
	HAVING COUNT(*) <> <cfqueryparam value="#Variables.termCount#" cfsqltype="cf_sql_numeric">
	</cfquery>
	<cfif q.recordCount gt 0>
		<cfreturn false>
	</cfif>
	<cfquery name="q" dbtype="query">
	SELECT rowNum, COUNT(*) AS cells
	FROM Variables.cellToBox
	GROUP BY rowNum
	HAVING COUNT(*) <> <cfqueryparam value="#Variables.termCount#" cfsqltype="cf_sql_integer">
	</cfquery>
	<cfif q.recordCount gt 0>
		<cfreturn false>
	</cfif>
	<cfquery name="q" dbtype="query">
	SELECT colNum, COUNT(*) AS cells
	FROM Variables.cellToBox
	GROUP BY colNum
	HAVING COUNT(*) <> <cfqueryparam value="#Variables.termCount#" cfsqltype="cf_sql_integer">
	</cfquery>
	<cfif q.recordCount gt 0>
		<cfreturn false>
	</cfif>
	<cfset Variables.boxesValid = true>
	<cfreturn true>
</cffunction>

<cffunction name="setCellBox" returntype="boolean" access="public" hint="Set the box number for a given cell, returning TRUE for success or FALSE for an unacceptable cell/box combination.">
	<cfargument name="rowNum" type="Numeric" required="yes">
	<cfargument name="colNum" type="Numeric" required="yes">
	<cfargument name="boxNum" type="Numeric" required="yes">
	<cfset var r = Arguments.rowNum>
	<cfset var c = Arguments.colNum>
	<cfset var b = Arguments.boxNum>
	<cfset var q = Variables.cellToBox>
	<cfif not (inRange(b) and inRange(r) and inRange(c))>
		<cfreturn false>
	</cfif>
	<cfset Variables.boxesValid = false>
	<cfquery name="q" dbtype="query">
	SELECT rowNum, colNum, boxNum
	FROM q
	WHERE NOT ((rowNum = <cfqueryparam value="#r#" cfsqltype="cf_sql_integer">) AND (colNum = <cfqueryparam value="#c#" cfsqltype="cf_sql_integer">))
	UNION ALL
	SELECT rowNum, colNum, <cfqueryparam value="#b#" cfsqltype="cf_sql_integer"> AS boxNum
	FROM q
	WHERE ((rowNum = <cfqueryparam value="#r#" cfsqltype="cf_sql_integer">) AND (colNum = <cfqueryparam value="#c#" cfsqltype="cf_sql_integer">))
	</cfquery>
	<cfset Variables.cellToBox = q>
	<cfreturn true> 
</cffunction>

<cffunction name="boxFromCell" returntype="Numeric" access="private">
	<cfargument name="rowNum" type="Numeric" required="yes">
	<cfargument name="colNum" type="Numeric" required="yes">
	<cfset var q = "">
	<cfquery name="q" dbtype="query">
	SELECT boxNum
	FROM Variables.cellToBox
	WHERE ((rowNum = <cfqueryparam value="#Arguments.rowNum#" cfsqltype="cf_sql_integer">) AND (colNum = <cfqueryparam value="#Arguments.colNum#" cfsqltype="cf_sql_integer">))
	</cfquery>
	<cfreturn q.boxNum>
</cffunction>

<cffunction name="inRange" returntype="boolean" access="private">
	<cfargument name="n" type="Numeric" required="true">
	<cfreturn (int(n) eq n) and (n gte 1) and (n lte Variables.termCount)>
</cffunction> 

</cfcomponent>